package com.cn.codebrush.动态规划;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Boolean
 * @Date 2022/7/14 18:21
 * @Version 1.0
 */
public class No115不同的子序列 {
    public static void main(String[] args) {
        int[] nums = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(numDistinct("babgbag","bag"));
		/*"dbaaadcddccdddcadacbadbadbabbbcad"
		"dadcccbaab"*/
        //System.out.println(grayCode(4));  // 16
        //System.out.println(1^3);

    }


    /*

		dp[i][j]显然要从dp[i-1][?]递推而来。立即思考dp[i-1][j], dp[i-1][j-1]分别与dp[i][j]的关系。
因为少一个字符，自然而然从当前字符着手。考察si的第i个字符(表为s[i])和tj的第j个字符(表为t[j])的关系。
若s[i] ≠ t[j]：那么s_i中的所有t_j子序列，必不包含s[i]，即s_i-1和s_i中tj的数量是一样的，得到该情形的转移方程:

		若s[i] = t[j]：假设s_i中的所有t_j子序列中，包含s[i]的有a个，不包含的有b个。
		s_i中包含s[i]的子序列个数相当于s_i-1中t_j-1的个数，
		不包含s[i]的子序列个数与上一种情况一样，于是得到该情形的转移方程：*/



    public static int numDistinct1(String s, String t) {
        if(s.length() < t.length()) return 0; // s长度小于t时，s中不会出现t
        int ns = s.length(), nt = t.length();
        char[] chss = s.toCharArray(), chst = t.toCharArray();
        int[][] dp = new int[ns + 1][nt + 1];
        for(int i = 0; i <= ns; i++) dp[i][0] = 1;
        for(int i = 1; i <= ns; i++){
            for(int j = 1; j <= nt; j++){
                dp[i][j] = dp[i - 1][j] + (chss[i - 1] == chst[j - 1] ? dp[i - 1][j - 1] : 0);
            }
        }
        return dp[ns][nt];
    }



    /**
     * 回溯超时
     */
    static List<String> reslist = new ArrayList<>();
    public static int numDistinct(String s,String t) {
        numDistinctHelper(s,t,"",0);
        return reslist.size();

    }
    public static void numDistinctHelper(String s,String t,String temp,int start) {
        if(temp.equals(t)){
            reslist.add(temp);
            return;
        }
        if(temp.length()>t.length()){
            return;
        }

        for(int i=start;i<s.length();i++){
            temp = temp+s.substring(i,i+1);
            numDistinctHelper(s,t,temp,i+1);
            temp = temp.substring(0,temp.length()-1);
        }

    }
}
